I. INTRODUCTION:

The problem of controlling a mobile robot and planning its trajectory is dominated by the fact that the robot's knowledge of the world is constantly in flux [3]. This is caused by the variation of the environment itself, by error in the robot's reckoning of its own position over time, and by its poor ability to make accurate and precise measurements of the environment [2]. Complicating the problem further is the complexity inherent in a robotic system. The robot must integrate sensor information about itself and its environment from a large variety of sensor modalities which are fraught with error. Its control actions are limited and constrained. It must guarantee its own safety in real-time in the presence of sudden and unexpected changes in the environment, while completing its mission with as little cost or in as little time as possible. Moreover, the robot must learn its environment as it encounters it [1].

As the field of robotics has developed, increasingly more of these challenges have been addressed at a time. In the 1950s, the earliest robots were able only to achieve basic locomotion. In the 1970s and 80s, the optimal completion of global objectives dominated the active research. Later, real-time constraints gained attention at the cost of optimal planning. Field robotics has moved in recent years out of controlled laboratory and office environments into outdoor environments where less and less a priori knowledge of the structure of the world can be assumed. Sensing has shifted from SONAR and IR, to accurate and modellable LIDAR scanning, to color vision, both within and beyond stereo range. Moreover, robots have accelerated drastically, from 1969 Shakey's 2 meters/hour [30] to 2005 Stanley's 70 miles/hour.

The robotics community continues to be challenged by several issues:

1. unknown unstructured environments,

2. sensor errors,

3. control constraints,

4. real-time guarantees,

5. global objectives,

6. dynamic obstacles

A. Control Architectures

Figure 1 Control architecture

This canonical architecture provides two layers (using the notation of Arkin [4]): reactive and deliberative. The reactive low-level controllers are decoupled from the deliberative planner, allowing the controllers to address real-time constraints while the planner addresses global objectives. The idea behind the low-level controllers is that each controller, or behavior, uses a small set of sensor measurements with a simple reasoning process to control

the robot for some narrowly-defined semantic purpose. For example, a behavior may be dedicated to preventing the robot from driving into suddenly appearing and unanticipated obstacles through laser data, or to forbid the robot to execute motion commands that would cause it to roll or crash. This behavior-based method of controlling a robot has received great attention in the robotics community [4, 7, 8, 13, 22, 28].

The global and local maps are used to handle sensor and localization error. The incremental map construction process is to be done in such a way as to account for sensor error as well as to incorporate new or changing information about the environment. The global planning block is intended to dynamically re-plan given the global map's changing opinion about the world. The reactive layer meets real-time constraints, while the deliberative layer is likely to require computation time dependent on the problem size. The reactive layer considers only \local" information, while the global layer considers the entire world. This two-layer approach is appropriate and sufficient for the work later described in this thesis. Note, however, that it is also common to divide the architecture into additional layers, allowing for finer control of how far and for how long a planning algorithm may operate. See for example [29, 30]. In [16], the deliberative layer is split into a regional waypoint planner which operates over some distance, and a subregional planner that provides precise paths for the underlying control layer.

Note the one-way flow of information: from the sensors, through the mapping processes, through the planning block, down into the controllers block, and finally out to the motor control.

II. PATH PLANNING:

Over the historical development of robotics, the preferred manner in which planning has been incorporated into robotic architectures has changed, and can be divided into a few distinct time periods. The earliest forays into robotics were able only to attack a small part of the navigation problem; the technological challenges were too difficult to do anything more significant. Roboticists focused on building systems that could demonstrate some semblance of intelligence. Perhaps the first such example is from 1953, W. Grey Walter's turtles, Elmer and Elsie [24]. They were very simple rolling machines that sensed light and exhibited phototaxis (the behavior of driving towards or away from a light source). They stored no information about the environment, and operated purely on what their sensors detected instantaneously. Hence, planning was omitted entirely. This work focused on basic behavioral functionality without any notion of (complicated) global objectives or control constraints.

In the 1970s, the classic Artificial Intelligence approach became popular, where planning was the focus of extensive study. Known as the deliberative approach [13] (also as sense-plan-act [30]), the robot would make a sensor sweep of the environment, plan the optimal (in some sense) action to take next, and then execute that plan until the next sensor sweep finished. Deliberative methods often use a complex model of the environment and the robot, especially within the classic AI framework. Consequently, such planning has a fatal flow: it often takes too much time and while the planning process runs, the world changes. As a result, the plan is often immediately invalidated, and the planning effort wasted. Moreover, this approach calls for an accurate and precise model of the environment and robot that is typically impossible or too expensive to come by. Under this paradigm, global optimality was emphasized to the exclusion of real-time effectiveness. In the 1980s, the reactive (or behavior-based) approach attracted attention again, most famously with the work of Brooks [13, 14] who focused on constructing robots that entirely omitted planning. While attractive because each behavior is based on minimal modelling of the robot and the world, methods inspired by or related to this approach are subject to the presence of local minima and are unable to escape from simple traps in the environment [8, 26]. That is, a behavior-based robot, without the benefit of memory or spatial knowledge of sufficient extent would become stuck in a cul-de-sac or caught \like a °y at a window".

The lesson: memory, modelling, and planning to some degree are generally needed. In recent years, activity in robotics has swelled. Technological advances such as dramatically increasing computational power, memory size and communication bandwidth have lessened some of the old challenges of robotics. Furthermore, the community has more and more experience with the hardware challenges of building reliable robust platforms that can run for extended periods of time even in ever harsher environments. There exists also a push by funding agencies to produce practical robotics that run without human assistance in outdoor unknown environments, with sensing based on vision, and with the task of operating in a complex active environment with long-term global objectives. Such projects include PerceptOR, the Learning Applied to Ground Robots project, the DARPA Grand Challenge I and II, and most recently DARPA's Urban Challenge. One of the lessons learned from the community is that the desire for optimal planning

is outweighed by the need for a \good" plan now [24]. As a result, approximate solutions to the problem of path planning which meet the time-critical constraints of the robot may be (and often are) preferable to a slow optimal one.

III. WORLD MODELS AND PATH PLANNING:

World models are usually divided roughly into two categories: topological (route, qualitative) and metric (layout, grid-based) models [11]. At present, lots of researches have produced a great variety of path planning methods [30, 27].

3.1 Topological Maps

Topological maps describe the connectivity of specific places called landmarks or gateways. These maps are represented in a form of a graph, where nodes are distinct places and edges are connections between them. The value of an edge may reflect then traversability of the respective segment of the path. Additional information may be attached to edges, such as direction, approximate distance, or the behaviours needed to navigate that path. If the robot finds a landmark and it appears on a map, the robot is localized with respect to the map. Examples of topological approaches include the works [16, 32, 24]. Widely used generalized Voronoi diagrams (GVD) also fall into this category [7]. GVD is a mapping method that tends to minimize the distance between the robot and obstacles on the map. The diagram consists of the lines constructed from all points that are equidistant from two or more obstacles in the plane. Hierarchical generalized Voronoi graphs (HGVG) is a roadmap that is an extension of GVD into higher dimensions then two. Choset [8] introduces technique to incrementally construct the HGVG as the robot explores its unknown static environment using only line of sight information.

3.1.1 Path Planning on Topological Maps

Paths can be computed between to points using standard graph algorithms, such as the classical Dijkstra’s single source shortest path algorithm [10]. The Voronoi diagram has a significant weakness in the case of limited range localisation sensors, since path planning algorithm maximises the distance between the robot and objects in the environment.

However, the number of paths from one place to another is limited by the number of edge combinations.

3.2 Metric Maps

Metric maps capture geometric properties of the environment. The number of different map representations is very large; none of them is dominant. The most common ones are regular grids and quad trees (and their 3D extension, octrees). Regular grid is a two-dimensional array of square elements (called pixels).

Regular grids are often called as occupancy grid, because each element in the grid will hold a value representing whether the location in space is occupied or empty [21]. Unfortunately, regular grids do not scale up very well. The size of the map grows with the size of the environment and path planning becomes computationally expensive. On a coarse grid, path planning is faster but obstacles are expanded on the grid and narrow corridors can disappear. One commercial robot that uses a standard occupancy grid is the Cye robot [2]. Also the tour-guide robots Minerva [22] and Rhino [4] are using occupancy grids. Quad trees are recursive grids. They are created by recursively subdividing each map square with non-uniform attributes into four equal-sized sub-squares.

The division is repeated until a square is uniform or the highest resolution is reached. Quad trees reduce memory requirements hereby allowing efficient partitioning of the environment. A single cell can be used to encode a large empty region [18].

However, the distinction between metric and topological maps has always been fuzzy, since virtually all topological approaches rely on geometric information. In practice, metric maps are finer grained than topological ones.

2.1.2.1 Path Planning on Metric Maps

Most world representation can be converted to graphs (e.g. cell decompositions, 4-connected and 8-connected grids, etc.). Typically graph-based path planners rely on A* or D* algorithms [6, 29] or on their modification (Incremental A* [21], Focussed D* [10], D* Lite [20], Delayed D* [13]). These algorithms generate shortest paths reducing computational complexity in case of highly connected graphs such as regular grids.

A* algorithm finds a path as good as found by Dijkstra’s algorithm but does it much more efficiently using an additional heuristic to guide itself to the goal. Dijkstra’s algorithm uses a best first approach. It works by visiting nodes in the graph starting from the start point and repeatedly examining the closest not-yet examined node until it reaches the goal. A* always first expands the node with the best cost calculated by f (n) = g(n) + h(n) . Where g(n) represents the cost of the path from the starting point to the node n , and h(n) represents the heuristic estimated cost from the node n to the goal. Usually, for calculating the heuristic cost, the Manhattan or the Euclidean distance is used.

D* is the dynamic version of A* producing the same result but much faster in dynamic environments. In a sense of replanning A* is computationally expensive because it must replan the entire path to the goal every time new information is added. In contrast, D* does not require complete replanning since it adjusts optimal path costs by increasing and lowering the cost only locally and incrementally as needed. Expansions of D* algorithm, like Focussed D*, D* Lite, Delayed D*, are accordingly even more efficient.

Potential fields planners are very widely represented, since they are extremely easy to implement. The potential field method treats the robot as a point under the influence of an artificial potential field. The goal acts as an attractive force on the robot and the obstacles act as repulsive forces. Such an artificial potential field smoothly guides the robot to the goal while simultaneously avoiding known obstacles. While potential field planners follow the gradient descent of the field to the goal they always find the shortest path from every possible start point. Potential fields have become a common tool in mobile robot application in spite of the local minima problem [6]. Harmonic functions can be used to advantage for potential field path planning, since they do not exhibit spurious local minima [9].

A popular family of path planning methods on grids is wavefront-based planners. They are based on potential fields, but do not have local minima problem [2]. The basic principle is that the configuration space is considered to be a conductive material with heat radiating out from the initial node to the goal node. Finally the heat will spread and reach the goal, if there is a way. The optimal path from all grid elements to the goal can be computed as a side effect. The distance transform planners are well-known wave front-based planners propagating distance throughout each grid cell in an outward direction from the specified goal point to the start point filling the entire free space. The optimal path from all grid elements to the goal is then found by using the steepest descent trajectory. Zelinsky introduced a safe path transform method in [20]. In addition to propagating a distance wavefront from the goal, another wavefront is propagated which is a combination of the distance from the goal together with a measure of the discomfort of moving near obstacles. In [15] distance transform is extended with linear vector combination to estimate shortest global path and obtain the safe local direction in which a mobile robot moves safely in a local environment. Trulla also is one of the many wavefront types of path planners [30]. This algorithm initially computes all possible paths from all possible locations to the goal. Trulla output is a potential field-like representation of the best direction the robot should take from any location in the map to the goal, given the a priori map and terrain preferences.

2.1.3 Hybrid Approaches

Frequently, metric and topological methods are used together. Those hybrid methods try to combine the advantages of metric-based and topological planning approaches, since both paradigms have strengths and weaknesses.

For example, topological approaches often have a difficulty determining distinct places if they look alike. This can be caused by sensor noise and aliasing. Also, since sensory input usually depends strongly on the viewpoint of the robot, it may fail to recognize geometrically nearby places even in static environments. All this makes construction and maintenance of large-scale maps difficult, particularly if sensor information is highly ambiguous. The key advantage of topological representation is their compactness, what is the main shortcoming of the metric maps. Due to compactness, topological representation permits faster planning than the metric approach. On the other hand, metric maps permit much more detailed path planning due to the high resolution. Since topological approach usually does not require the exact determination of the geometrical position of the robot, it often recovers better from drift and slippage-phenomena that must constantly be monitored and compensated on metric-based approaches.

Byun and Kuipers [27] used a multi-level spatial hierarchy. The lowest level is identifying landmarks. The next layer up is topological, represented on a relational graph, which supports planning and reasoning. The uppermost level is metric, where the agent learns the distances and orientation between the landmarks and can place them in fixed coordinate system. Fabrizzi and Saffiotti [12] extract the topological map from the previously created grid map analyzing the shapes of the free spaces. The run [10] generates topological maps on top of the grid-based maps by partitioning the latter into coherent regions, separated by critical lines. Critical lines correspond to narrow passages such as doorways. By partitioning the metric map into a small number of regions, the number of topological entities is several orders of magnitude smaller than the number of cells in the grid representation. Poncela et al. [13] perform exploration path planning on two levels: global planning is performed on topological level and local planning is performed on metric level. Such representation permits exploration in a fast and efficient way. Kruusmaa [22, 23] uses case-base reasoning with a grid map. A grid-based map permits detailed path planning and case-base stores travelled paths with traverse ability information of those paths in a form of a simple cost function that is easy to update.

III. Path Planning using Wave front Algorithm:

The wavefront algorithm involves the breadth first search technique, searching along the horizontal plane of the graph, beginning at the start point propagating out until it reaches the goal point. A grid of squares is created from the map using an appropriate size of square. Each square is initialized to a numerical value of 0. Squares known to contain a physical object or part of an object are assigned a numerical value of 1. The goal point is then identified and allocated a value of 2. To create the wavefront values, any squares which surround the goal point are given a higher number depending on how close they are to the goal point. A value of 3 is assigned to the squares adjacent to the goal point, with the value of 4 assigned to the squares adjacent to those squares having a value of 3, and so on. Once the start point is assigned a numerical value, the algorithm then proceeds to select the lowest value square nearest the start point. It is marked as a waypoint. Then the algorithm moves to the selected square and selects the nearest square having the lowest value. It is also marked as the waypoint. The sequence is repeated until the goal point is reached. This creates the safe path, in terms of a series of waypoints, from the start point to the goal point. However, some waypoints can be eliminated if the path from the previous waypoint to the next waypoint does not cross through the obstacle. Therefore, the algorithm can iteratively eliminate some waypoints and it is repeated until no other waypoint can be eliminated. Figure 1 displays an example of the wavefront values.

IV. CONCLUSION:

Although the simulated robot was able to effectively navigate in the simulated experiments under the odometry system provided by the Player/Stage simulator, these experiments do not guarantee that the real robot will perform in the same way when the same experiments are conducted under real conditions, primarily because the simulated robot model does not include any of the robot dynamics, and the sensors are modeled as being ideal. Furthermore, the simulated environment was relatively uncluttered and did not contain other moving obstacles, such as humans or other robots that could have obstructed its performance. However, since the simulated environment was similar to the actual conditions in the laboratory, it is postulated that the robot will achieve an acceptable level of performance under real conditions.

V. REFERENCES:

1. Siegwart, R. and I.R. Nourbakhsh, Introduction to Autonomous Mobile Robots. 2004.

2. Khatib, O., Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. The International Journal of Robotics Research, 1986. 5(1): p. 90-98.

3. Arkin, R.C., Motor Schema-Based Mobile Robot Navigation. The International Journal of Robotics Research, 1989: p. 92-112.

4. Brooks, R.A., A Robust Layered Control System for a Mobile Robot. IEEE Journal of Robotics and Automation, 1986. RA-2(1): p. 14-23.

5. Arkin, R.C., Motor schema based navigation for a mobile: An approach to programming by behavior. Proceedings IEEE International Conference on Robotics and Automation, 1987. 4: p. 246-271.

6. Gerkey, B.P., et al., Most Valuable Player: A Robot Device Server for Distributed Control. Proceedings of the IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2001: p. 1226-1231.

7. Collett, T.H.J., B.A. MacDonald, and B. Gerkey, Player 2.0: Toward a Practical Robot Programming Framework. Proceedings of the Australasian Conference on Robotics and Automation (ACRA 2005), 2005.

8. Arkin, R.C., Behavior-Based Robotics. 1 ed. Bradford Book. 1998: MIT Press. 491.

9. Egerstedt, M., Behavior Based Robotics using Hybrid Automata. Proceedings of the Third International Workshop on Hybrid systems: Computation and Control, 2000: p. 103-116.

10. Sahota, M.K., Action Selection for Robots in Dynamic Environments through Inter-behaviour Bidding. Proceedings of the Third International Conference on Simulation of Adaptive Behavior, 1994: p. 138-142.

11. Taliansky, A. and N. Shimkin, Behavior-Based Navigation for an indoor Mobile Robot. 21st IEEE Convention of the Electrical and Electronic Engineers in Israel, 2000: p. 281-284.

12. Borenstein, J. and Y. Koren, Real-time Obstacle Avoidance for Fast Mobile Robots. 1989 IEEE. Reprinted, with permission, from IEEE Transactions on Systems, Man, and Cybernetics, 1989. 19(5): p. 1179-1187.

13. Mataric, M.J., The Robotics Primer. 2007

14. Jan Willemson1 and Maarja Kruusmaa, "Algorithmic Generation of Path Fragment Covers for Mobile Robot Path Planning". Tartu University, Estonia, 3rd IEEE Conference On Intelligent Systems September 2006.

15. Kristo Heero, "Path Planning and Learning Strategies for Mobile Robot in Dynamic Partially known Environment". Ph.D. thesis, may 2006. Tartu University Press.

16. G. Dudek and M. Jenkin, "Computational Principles of Mobile Robotics". Cambridge University Press, 2005.

17. R. L. Haupt, S. E. Haupt, "Practical Genetic Algorithms", Published by John Wiley and Sons, Inc., Hoboken, New Jersey, Second edition, 2004.

18. R. K. Bock and W. Krischer. Data Analysis Brief Book. Springer, Berlin, 1998. URL: (version current as of May 02, 2003).

19. D. Marsh. Applied Geometry for Computer Graphics and CAD. Springer-Verlag, New York, NY, 1999.

20. John H. Mathews and Kurtis K. Fink," Numerical Methods Using Matlab", 4th Edition, 2004, ISBN: 0-13-065248-2, USA.

21. Kenneth I. Joy, "Bernstein Polynomials", On-Line Geometric Modeling Notes of Computer Science Department, University of California, Davis, 2000.

22. B. Sturmfels. Solving Systems of Polynomial Equations. AMS, Providence, R.I., 2002.

23. Kuldeep Singh. "Engineering mathematics through applications". University of Hertfordshire, Department of Mathematics. Industrial press, New York, 2003.

24. Bernard K., Robert C., and Sharon C. "Discrete Mathematical Structures". Fifth edition, Pearson Prentice Hall press, U.S.A, 2004.

25. R. Murphy, "AI Robotics ", MIT press, 2000.

26. Loo C. K., and at el. "Mobile Robot Path Planning Using Genetic Algorithm and Travers ability Vector Method". Intelligent Automation and Soft Computing, Vol.1, pp. 51-64, 2004.

27. V. Lumelsky and A. Stepanov. "Path planning strategies for a point Mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, pp. 462-472, 1990.

28. C. Hocaoglu, A.C. Sanderson, "Planning Multiple Paths with Evolutionary Speciation", IEEE Trans. on Evolutionary Computation, Vol.5, No. 3, JUNE 2001.

29. J. A. Sauter, R. Mattnews, H. V. Parunak and S. Brueckner, "Evolving Adaptive Pheromone Path Planning Mechanisms", Proc. of the first Int. Conf. on Autonomous Agents and Multi-Agent Systems AAMAS, 2002, Italy.

30. J.TU, S.X. Yang, "Genetic Algorithm Based Path Planning for a Mobile Robot", Int. Conf. on Robotics and Automation, pp. 1221-1226, Taipei, Taiwan, Sep 14-19. 2003

31. J. H. Holland, "Adaptation in Natural and Artificial Systems", Ann Arbor, MI, The University of Michigan Press, 1975

Received on 11.11.2011 Accepted on 14.12.2011

Int. J. Tech. 1(2): July-Dec. 2011; Page 143-148